/*
 * @lc app=leetcode id=35 lang=cpp
 *
 * [35] Search Insert Position
 */
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        int i = 0, j = len - 1;
        int mid, pos;

        while(i <= j) {
            mid = (i+j)/2;
            if (target == nums[mid]) {
                pos = mid;
                break;
            } else if (target > nums[mid]) {
                if (mid == len - 1 || (mid < len-1 && target <= nums[mid+1])) {
                    pos = mid + 1;
                    break;
                } else {
                    i = i+1;
                }
            } else {
                if (mid == 0 || (mid > 0 && target > nums[mid-1])) {
                    pos = mid;
                    break;
                } else {
                    j = j-1;
                }
            }
        }
        return pos;
    }
};

